#include "main/utils.h"
using namespace std;

int sum(const vector<vector<int>> &vec,
        const pair<int, int> &left_up,
        const pair<int, int> &right_bottom) {
  int row = vec.size();
  int col = vec[0].size();
  vector<vector<int>> help_vec;
  vector<int> tmp_vec(col, 0);
  help_vec.push_back(tmp_vec);
  for (int i = 0; i < row; ++i) {
    int row_sum = 0;
    tmp_vec.clear();
    tmp_vec.push_back(0);
    for (int j = 0; j < col; ++j) {
      row_sum += vec[i][j];
      tmp_vec.push_back(row_sum + help_vec[i][j + 1]);
    }
    help_vec.push_back(tmp_vec);
  }
  int row1 = left_up.first;
  int row2 = right_bottom.first + 1;
  int col1 = left_up.second;
  int col2 = right_bottom.second + 1;
  int ret = help_vec[row2][col2] - help_vec[row2][col1] - help_vec[row1][col2] + help_vec[row1][col1];
  return ret;
}

int main() {
  vector<vector<int>> vec = {{3, 0, 1, 4, 2},
                             {5, 6, 3, 2, 1},
                             {1, 2, 0, 1, 5},
                             {4, 1, 0, 1, 7},
                             {1, 0, 3, 0, 5}};
  pair<int, int> left_up = make_pair(2, 1);
  pair<int, int> right_bottom = make_pair(4, 3);
  int ret = sum(vec, left_up, right_bottom);
  cout << ret << endl;

  return 0;
}
